package com.company.OfferGuide;

public class 丑数 {

    public static void main(String[] args) {
        System.out.println(nthUglyNumber(10));
    }

    public static int nthUglyNumber(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int pow2 = 0;
        int pow3 = 0;
        int pow5 = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            int ugly = Math.min(Math.min(dp[pow2] * 2,dp[pow3] * 3),dp[pow5] *5);
            dp[i] = ugly;
            if (dp[pow2] * 2 == ugly) {
                pow2++;
            }
            if (dp[pow3] * 3 == ugly) {
                pow3++;
            }
            if (dp[pow5] * 5 == ugly) {
                pow5++;
            }
        }
        return dp[n - 1];
    }

}
